package q413_numberOfArithmeticSlices;

public class Solution_1 {
    /*
    动态规划的方法 时间空间复杂度都是o(n)
    用一个isArithmetic来记录当前i结尾的位置是否有一个等差数列 条件为nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]
    例如 1 2 3 1 2 3 4 5
    其中3 3 4 5即为true
    然后遍历isArithmetic 如果为true 那么dp[i] = dp[i - 1] == 0 ? 1 : dp[i - 1] + 1;
    也就是如果dp[i - 1] == 0 意味着刚好能够组成等差 此时dp为1 而如果上一个不是0 意味着前面也有一个等差数列 那么此时dp + 1
    对于 1 2 3 1 2 3 4 5 记录也就是 0 0 1 0 0 1 2 3 以5结尾为例 dp代表以5作为结尾的等差数列有3个
    所以dp的意义就是以nums[i]结尾的能够构成dp[i]个等差数列
    最后求和即可
     */
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }
        int[] dp = new int[nums.length];
        int ans = 0;
        boolean[] isArithmetic = new boolean[nums.length];
        for (int i = 2; i < nums.length; i++) {
            isArithmetic[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2];
        }

        for (int i = 0; i < nums.length; i++) {
            if (isArithmetic[i]) {
                dp[i] = dp[i - 1] == 0 ? 1 : dp[i - 1] + 1;
                ans += dp[i];
            }
        }

        return ans;
    }
}
